package leetcode_jz_offer;

/**
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素
 **/

import java.lang.reflect.Array;
import java.util.*;

/**
 * 思路：回溯
 * 1.定义递归函数：permutationHelper(i,sb) 表示当前排列为sb，下一个待填入的空位是第i个空位（下标从0开始）。那么该递归函数分为两个情况:
 *      1)i==n,我们填完了n个空位，sb放入答案数组中，递归结束
 *      2)i<n,考虑i填何字符，填入遍历到的未标记的字符，然后用标记bool标记已经填过的字符，然后继续下一个空位填写，即调用permutationHelper(i,sb)
 *      3)调完函数回溯时，我们需要要撤销该空位填的字符以及对该字符的标记，并继续向当前空位尝试填入其他没被标记过的字符
 * 2.去重（保证每个排列只出现一次）：每一个空位的重复字符只能被填写一次
 *      具体：对原字符串排序，保证相同的字符都相邻，在递归函数中，我们限制每次填入的字符一定是这个字符所在重复字符集合中「从左往右第一个未被填入的字符」
 *      即如下的判断条件：
 *      if (bool[j] || (j > 0 && !bool[j - 1] && s[j - 1] == s[j])) {
 *      //bool[j]:j没有被标记是false，此时判断后面若j-1没被标记且j-1与j对应值等，执行continue（重复字符的第一个才能执行调用，j在j-1后还和j-1一样自然不能调用）
 *       continue;
 *      }
 */
public class Num38_字符串的排列 {
    List<String> res;
    boolean[] bool;
    public String[] permutation(String s) {
        int a=2;
        res=new ArrayList<>();
        bool=new boolean[s.length()];
        //1.字符串中的字符进行排序，让重复的在一块
        char[] array=s.toCharArray();
        Arrays.sort(array);
        StringBuilder sb=new StringBuilder();
        //2.将有序字符串进行不同排列,结果存储在res中
        permutationHelper(array,0,s.length(),sb);
        //3.输出字符串数组
        int size=res.size();
        String[] strs=new String[size];
        for (int i = 0; i < size; i++) {
            strs[i]=res.get(i);
        }
        return strs;
    }

    //将字符串组合成不同的顺序排列，保存在StringBuilder中
    //递归+回溯
    private void permutationHelper(char[] array, int i, int length, StringBuilder sb) {
        if(i==length){
            //递归出口，填完了length个空位，sb内所有的内容保存到res中，返回即可
            res.add(sb.toString());
            return;
        }
        for (int j = 0; j < length; j++) {
            //去重
            if(bool[j]||(j>0&&!bool[j-1]&&array[j]==array[j-1])){
                continue;
            }
            //当前位置标记为已判断过
            bool[j]=true;
            sb.append(array[j]);//当前数字加入sb中
            //进行下一个位置的数字插入
            permutationHelper(array,i+1,length,sb);
            //回溯——撤销该空位填的字符以及对该字符的标记
            sb.deleteCharAt(sb.length()-1);
            bool[j]=false;
        }
    }
    //方法2：也是回溯但使用到Set去重
    Set<String> set=new HashSet<>();
    boolean[] b;
    public String[] permutation1(String s){
        char[] array=s.toCharArray();
        b=new boolean[s.length()];
        StringBuilder sb=new StringBuilder();
        dfs(array,0,sb);//从array的第一个索引遍历直到最后一个索引
        //得到了set集合，变为String[]
        int size=set.size();
        String[] res=new String[size];
        set.toArray(res);//set集合变为String[]（Set<String>），和下面注释掉的两行代码效果一样
//        int idx = 0;
//        for (String str : set) res[idx++] = str;
        return res;
    }

    private void dfs(char[] array, int i, StringBuilder sb) {
        int length=array.length;
        //递归终止条件：i遍历完最后一个字符后
        if(i==length){
            set.add(sb.toString());//set添加操作时就会去重
            return;
        }
        //循环判断下一个字符填的是哪个字母
        for (int j = 0; j < length; j++) {
            if(b[j])continue;//当前位不能放已经放过的字符
            b[j]=true;
            sb.append(array[j]);
            dfs(array,i+1,sb);
            //回溯——撤销该位置填的字符以及对该字符的标记
            sb.deleteCharAt(sb.length()-1);
            b[j]=false;
        }
    }

}
